package com.yulongtian.weekCompetition.month202302.week04;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author yulongTian
 * @create 2023-02-27 18:16
 */
public class Test04 {
    public static void main(String[] args) {

    }

    /**
     * Dijkstra方法
     * 1 设dis[x] 表示从起点到 x 的最短路
     * 设 y->x
     * 考虑所有 y，当我们更新 dis[x] 的时候，如果 dis[y]已经是最短路了
     * 那么 dis[x]的最短路程一定可以准确地算出来
     * <p>
     * 2 如何保证算出来的一定是最短路程
     * 数学归纳法+反证法
     * 一开始只有一个起点st
     * dis[st]=0 这是已经算好了
     * 从st开始 把st的邻居的距离（dis[]）都更新（此时不一定是算好的最短路程）
     * <p>
     * 从没有算好的 dis 里面，取出一个最小的
     * <p>
     * 3 这个取出来的一定是最好的
     *
     * @param grid
     * @return
     */
    public int minimumTime(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (grid[0][1] > 1 && grid[1][0] > 1) {
            return -1;
        }
        //否则答案一定存在（因为可以反复横跳来拖时间）
        //我需要知道到达 grid[i][j] 的最小时间 dis[i][j]
        //dis[i][j] 一定和（i+j）是同奇偶的
        //如果没有同奇偶 dis[i][j]+=1 就好
        //边权与格子的值和位置有关

        int[][] dis = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        }
        dis[0][0] = 0;
        //三元组队列 距离和坐标
        Queue<int[]> h = new LinkedList<>();
        //起始
        h.add(new int[]{0, 0, 0});
        while (!h.isEmpty()) {
            int[] poll = h.poll();
            int d = poll[0];
            int i = poll[1];
            int j = poll[2];
            if (i == m - 1 && j == n - 1) {
                return d;
            }
            int[][] temp = new int[][]{{i + 1, j}, {i - 1, j}, {i, j + 1}, {i, j - 1}};
            for (int[] ints : temp) {
                int x = ints[0];
                int y = ints[1];
                if ((0 <= x && x < m) && (0 <= y && y < n)) {
                    int nd = Math.max(d + 1, grid[x][y]);
                    nd += (nd - x - y) % 2;
                    if (nd < dis[x][y]) {
                        dis[x][y] = nd;
                        h.add(new int[]{nd, x, y});
                    }
                }
            }
        }
        return -1;
    }


}
